/**
 * N 皇后
 *
 * 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 *
 * 示例 1：
 * 输入：n = 4
 * 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 * 解释：如上图所示，4 皇后问题存在两个不同的解法。
 *
 * 示例 2：
 * 输入：n = 1
 * 输出：[["Q"]]
 *
 * 提示：
 * 1 <= n <= 9
 */

import java.util.ArrayList;
import java.util.List;

/**
 * N 皇后, 听说你很久了, 这次就让咱来解决下你, 我们看到题目, 有种解数独的既视感
 * 那就让我们来写吧, 我们需要处理好 行列斜(其实按照我们一层一层的来写可以不用管行的
 * 这里千万不要这么想, 因为我们使用格子里的数来表示这个格子的状态, 所以要是不管, 可能
 * 在回溯的时候变为负数), 因为我们深搜是一层一层深搜的, 所以我们要写好一层的字符串
 * 时间复杂度 : O(n! * n)
 * 空间复杂度 : O(n^2)
 *
 */

public class Main {

    // 定义全局变量
    List<List<String>> lists;
    List<String> list;
    int n;

    // 这里用 int 来表示格子状态, == 0 表示不会被攻击, > 0 表示会被攻击
    int[][] tmp;

    public List<List<String>> solveNQueens(int len) {

        // 初始化
        lists = new ArrayList<>();
        list = new ArrayList<>();
        n = len;
        tmp = new int[n][n];

        // 从第 0 层开始深搜
        dfs(0);
        return lists;
    }

    /**
     * 深搜
     *
     * @param k : 用来标识正在处理多少层
     */
    private void dfs (int k) {

        // 要是遍历到 第 n 层 说明已经遍历完, 出口
        if (k == n) {
            lists.add(new ArrayList<>(list));
            return;
        }

        // 同一层中有 n 个数
        for (int i = 0; i < n; i++) {

            // 要是这格的状态为不会被攻击就加入
            if (tmp[k][i] == 0) {

                // 扭转相关联的状态, 就是关联格子 +1
                changeStatus(k, i, 1);

                // 添加这行的字符串
                list.add(vaildString(i));

                // 深搜狭义层
                dfs (k + 1);

                // 恢复现场
                list.remove(list.size() - 1);

                // 在恢复状态的时候有个小细节, 我们之所以不用 boolean 来表示格子状态
                // 就是因为在恢复现场时, 要是 boolean 类型会让之前别的格子改变的状态
                // 一起改回不回受攻击, 所以我们用 int , 在恢复的时候进行关联格子 -1
                changeStatus(k, i, -1);
            }
        }
    }

    /**
     * 扭转相应的状态
     *
     * @param a
     * @param b
     * @param vaild
     */
    private void changeStatus(int a, int b, int vaild) {

        for (int i = 0; i < n; i++) {

            // 更改 |
            tmp[i][b] += vaild;

            // 更改 --
            tmp[a][i] += vaild;
        }

        for (int i = 0; i < n; i++) {

            // 更改 /
            if (a - i >= 0 && b + i < n) {
                tmp[a - i][b + i] += vaild;
            }
            if (b - i >= 0 && a + i < n) {
                tmp[a + i][b - i] += vaild;
            }

            // 更改 \
            if (a - i >= 0 && b - i >= 0) {
                tmp[a - i][b - i] += vaild;
            }
            if (a + i < n && b + i < n) {
                tmp[a + i][b + i] += vaild;
            }
        }
    }

    /**
     * 创建对应列的字符串
     *
     * @param k  对应层
     * @return   返回对应层的字符串
     */
    private String vaildString (int k) {
        StringBuffer ret = new StringBuffer();
        for (int i = 0; i < n; i++) {
            if (i != k) {
                ret.append(".");
            } else {
                ret.append("Q");
            }
        }
        return ret.toString();
    }


    // 测试用例
    public static void main(String[] args) {
        Main test = new Main();
        test.solveNQueens(4);
    }
}